<html>
<!-- $LastChangedDate: 2009-11-07 22:56:33 -0500 (Sat, 07 Nov 2009) $ -->
<!-- Copyright (C) 2004,2009 Jim Brooks http://www.palomino3d.org -->
<head>
<title>Palomino - 3D Math</title>
<link rel='stylesheet' type='text/css' href='docs.css'>
<link rel='icon' type='image/png' href='images/favicon.png'/>
</head>
<body>

<!-- ----------------------------------------------------------------------- -->
<h1>Palomino - 3D Math</h1>
<p>
&copy;2004,2009&nbsp;&nbsp;Jim E. Brooks
&nbsp;&nbsp;<a href='http://www.palomino3d.org'>http://www.palomino3d.org</a>
</p>
<hr>
<ul>
  <li><a href='index.html'>Index</a></li>
  <li><a href='#Coordinate Systems'>Coordinate Systems</a></li>
  <li><a href='#Normal Vectors, Cross Products, Dot Products'>Normal Vectors, Cross Products, Dot Products</a></li>
  <li><a href='#Matrix'>Matrix</a></li>
  <li><a href='#Matrix Rotation'>Matrix Rotation</a></li>
</ul>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Coordinate Systems'></a>
<h2>Coordinate Systems</h2>
<p><!--date-->[2004]</p>
<p>
These are the coordinate systems a 3D vertex is transformed thru:
<ol>
<li><a href='#Local Coordinate System'>local</a></li>
<li><a href='#World Coordinate System'>world</a></li>
<li><a href='#Eye Coordinate System'>eye</a></li>
<li><a href='#Perspective Coordinate System'>perspective</a></li>
<li><a href='#Viewport Coordinate System'>viewport</a></li>
<li><a href='#Normal Coordinate System'>normal</a></li>
</ol>
</p>
<p>
Transformation of a 3D vertex thru coordinate systems:
</p>
<p>
<b><font color='darkgreen'>Local <img src='images/arrowGreen.gif' hspace='8'> World <img src='images/arrowGreen.gif' hspace='8'> Eye </font><font color='darkred'><img src='images/arrowRed.gif' hspace='8'> Perspective <img src='images/arrowRed.gif' hspace='8'> 2D viewport</font></b>
</p>
<p>
<font color='darkgreen'>Green</font> indicates transformations done by the engine.
<br><font color='darkred'>Red</font> indicates transformations done by the gfxsys.
<br>Local:World and World:Eye can be combined by matrix multiplication.
</p>
<a name='Local Coordinate System'></a>
<h3>Local Coordinate System</h3>
<p>
3D objects have their own local coordinate system.
Also known as object coordinates.
</p>
<a name='World Coordinate System'></a>
<h3>World Coordinate System</h3>
<p>
The world coordinate system contains the simulated world (the scene to be rendered).
It is mapped to the eye coordinate system by the <a href='#Eye Matrix'>Eye Matrix</a>.
</p>
<p>
Altitude correlates to a positive world Y coordinate.
(X,Z) correlates to a 2D position ("ground coordinates") somewhere on the modeled terrain/land.
</p>
<a name='Eye Coordinate System'></a>
<h3>Eye Coordinate System</h3>
<p>
The eye coordinate system stays mapped to the viewport of the window system.
Eye vertexs are the final result of all transformations.
They are submitted the gfxsys.
</p>
<p>
(X,Y) eye coordinates correlate to (X,Y) viewport coordinates.
An eye Z coordinate measures the distance from the eye/viewpoint.
For an eye vertex, (X,Y) are divided by Z to project
the vertex onto the viewport (window).
This projection creates the illusion of perspective on a 2D computer display.
</p>
<a name='Perspective Coordinate System'></a>
<h3>Perspective Coordinate System</h3>
<p>
Eye coordinates are transformed by the gfxsys into perspective coordinates.
The view frustum (which exists in eye space) is mapped to perspective coordinates.
<a name='Viewport Coordinate System'></a>
</p>
<h3>Viewport Coordinate System</h3>
<p>
This is the 2D window on the computer's window system.
<a name='Normal Coordinate System'></a>
</p>
<h3>Normal Coordinate System</h3>
<p>
Every normal vector calculated from a cross product exists in its own coordinate system.
Its origin (0,0,0) is mapped to a <i>local</i> vertex of the polygon
on which it is perpendicular to.
Normals depend on the object's transformation in local space.
For example, if the vertexs of an aileron are rotated in local space,
all normals on the aileron must be rotated likewise (or recalculated)
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Normal Vectors, Cross Products, Dot Products'></a>
<h2>Normal Vectors, Cross Products, Dot Products</h2>
<p><!--date-->[2004]</p>
<p>
The result of the cross product of two vectors extending from a shared vertex on a planar polygon is a normal vector.
<code>CrossProduct()</code> uses the first vertex argument as the origin of the normal vector.
The resulting vertex on the normal vector is stored in a distinct <code>NormalVertex</code> type
as it exists in its own coordinate system.
</p>
<pre>
/*****************************************************************************
 * Calculate a cross product of two vectors which yields a normal vector
 * that is perpendicular to the plane containing the two source vectors.
 * Note: The cross product won't be unit length.
 * c = a x b
 *****************************************************************************/
INLINE NormalVertex
CrossProduct( const Vector3& v1, // origin of normal vector
              const Vector3& v2,
              const Vector3& v3 )
{
    fp a, b, c;
    fp d, e, f;

    a = v2.x - v1.x;
    b = v2.y - v1.y;
    c = v2.z - v1.z;

    d = v3.x - v1.x;
    e = v3.y - v1.y;
    f = v3.z - v1.z;

    return NormalVertex( b*f - c*e,
                         c*d - a*f,
                         a*e - b*d );
}
</pre>
<p>
A dot product is calculated from two vectors extending from a shared vertex.
The result is a single value (scalar).
If the angle between the two vectors is between 0' and 90',
then the dot product will be a positive value.
Normal vector, cross products, and dot products are used for
<a href='#Culling Polygons'>culling polygons</a>
which aren't facing the viewpoint.
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Matrix'></a>
<h2>Matrix</h2>
<p><!--date-->[2004,2007/04]</p>
<p>
A compact 4x3 matrix is used:
<pre>
{ Xx, Xy, Xz,    // X axis
  Yx, Yy, Yz,    // Y axis
  Zx, Zy, Zz,    // Z axis
  Ox, Oy, Oz };  // origin
</pre>
</p>
<p>
The 9 axis coefficients and the origin are used for matrix rotation and translation.
</p>
<p><font size='-1'>
OpenGL is based on a 4x4 matrix.  OpenGL has a 4th column for homogeneous coordinates.
Homogenous coordinates applies to projection and scaling.
The engine only rotates and translates non-homogeneous coordinates,
and never exchanges matrixs with OpenGL,
thus allowing a minimized 4x3 matrix to be used.
</font></p>
<p>
A vertex is rotated by:
<br>(one coordinate system is rotated relative to another)
<pre>
x' = x*Xx + y*Xy + z*Xz
y' = x*Yx + y*Yy + z*Yz
z' = x*Zx + y*Zy + z*Zz
</pre>
</p>
<p>
A vertex is translated by:
<br>(one coordinate system is translated relative to another)
<pre>
x' = x + Ox
y' = y + Oy
z' = z + Oz
</pre>
</p>
<a name='Eye Matrix'></a>
<h3>Eye Matrix</h3>
<p>
The eye matrix maps the world coordinate system to the eye coordinate system.
A peculiarity of the eye matrix is that its offsets (Ox,Oy,Oz) are all negative.
</p>
<a name='Object Matrix'></a>
<h3>Object Matrix</h3>
<p>
The Object class has a
<a href='#Transform Hierarchy'>transform hierarchy</a>
which transform vertexs from local space to eye space.
</p>
<h3>Transpose Matrix</h3>
<p>
A matrix maps one coordinate system to another.  The mapping is directed.
The mapping can be reversed by transposing a matrix.  This is done by
turning each row into a column.
Note: a <i>transpose matrix</i> and an <i>inverse matrix</i> are different mathematical concepts.
</p>
<pre>
 [ Xx Xy Xz ]     [ Xx Yx Zx ]
 [ Yx Yy Yz ]     [ Xy Yy Zy ]
 [ Zx Zy Zz ]     [ Xz Yz Zz ]
</pre>
<p>
An example of using a transpose matrix is the animation
of tracer bullets in a first-person view.
The eye matrix maps world-to-eye coordinates.
The tracer bullets are modeled starting from a local coordinate system.
What's needed is a local matrix that maps local-to-world coordinates
and it must be aligned with the eye matrix.
The transpose of the eye matrix is that local matrix.
Although the transposed eye matrix maps eye-to-world coordinates, it can work
because the result of the transformation is in world coordinates (on the output side),
and by substituting local coordinates instead of eye coordinates on the input side.
A copy of the eye matrix used as the local matrix wouldn't work because
the two transformations from local-to-world and world-to-eye would nonsensically
pass thru the eye matrix (which is meant for the latter transformation only).
</p>

<!-- ----------------------------------------------------------------------- -->
<hr>
<a name='Matrix Rotation'></a>
<h2>Matrix Rotation</h2>
<p><!--date-->[2004,2007/04]</p>
<p>
Two different descriptions about rotating a 3D matrix around its axises:
<br><a href='../obsolete_historical/archaic.html#Matrix Rotation 1990'>Matrix Rotation [1990]</a>
<br><a href='#Matrix Rotation 2004'>Matrix Rotation [2004]</a>
</p>

<a name='Matrix Rotation 2004'></a>
<h3>Matrix Rotation [2004]</h3>
<p><i><!--date-->[Updated 2007/04.  This code evolved into the Matrix class.]</i></p>

<!--
Note: These notes were written in Jan 2004.  The "3D" asm program was capable of
local matrix rotation but that was something I didn't document in 1989..1991
(neither on paper nor in the assembly code).
C++ code for local matrix rotation is in opengl/gl_common/gl_math.cc (Jan 2004).
-->

<p><i>The following notes were written in 2004 as a rewrite of notes from 1990.
It distinguishes the two ways to rotate a matrix.
Rotation around a fixed coordinate system is for rotating a first-person view (Eye).
Rotation around a local coordinate system is for rotating dynamic objects.
Both are implemented [2007] as Matrix::RotateFixed() and Matrix::RotateLocal().
</i></p>

<p>
This matrix rotation formula <!--(which I documented on paper)-->
is actually rotation around a fixed coordinate system
(this fact wasn't originally documented).
For example, in the formula for rotation around the X axis...
</p>
<p><pre>
X Pitch
-------

c = cos(radian)
s = sin(radian)

m[Yx] = m[Yx]*c - m[Zx]*s  // Y = Ycos - Zsin
m[Yy] = m[Yy]*c - m[Zy]*s
m[Yz] = m[Yz]*c - m[Zz]*s

m[Zx] = m[Yx]*s + m[Zx]*c  // Z = Ysin + Zcos
m[Zy] = m[Yy]*s + m[Zy]*c
m[Zz] = m[Yx]*s + m[Zz]*c
</pre></p>
<p>
...notice that the X coordinate doesn't change (X is 1:1).  Thus the rotation
is around a fixed X axis.  The formulas are correct for rotating the viewpoint
(first-person perspective) or in other words the eye coordinate system.
</p>
<p>
But to rotate an object relative to its own local coordinate system,
additional math must be done.  Recall that a local coordinate system
is mapped to the eye coordinate system.  After random rotations around
all 3 axises of the local coordinate system, eventually,
the X coordinate, for instance, should be transformed to a different value.
</p>
<p>
These are the steps to rotate a coordinate system relative to itself (local rotation):
</p>
<ol>
<li>Let m be the matrix that defines a local coordinate system.
</li>
<li>Load identity into temporary matrix r.
</li>
<li>Rotate matrix r around one of its axises using the formula for rotation around a fixed axis.
</li>
<li>Transform matrix r thru matrix m. Ie, transform r thru m as if r were the rotated coordiates (1.0, 1.0, 1.0).
</li>
<li>m = r
</li>
</ol>
<p>
The trick is transforming the result of the rotation of a fixed coordinate system
into the local coordinate system.
</p>

<!-- gfx_math_matrix.hh [Aug 2006] -->
<pre>
/*****************************************************************************
 * Rotate a matrix around a fixed axis.
 * This function is suited to rotating the viewpoint/eye.
 * The word "fixed" should be clear by looking at the math.
 * Eg, the value of the X coord won't be changed by a rotation around the X axis.
 *****************************************************************************/
void
Matrix::RotateFixed( uint axis, Radian rad )
{
    FPM s, c; SinCos( rad, s, c );
    Matrix n = *this;  // dest = src
    switch ( axis )
    {
        // X : Pitch
        case AXIS_X:
        n[Yx] = m[Yx]*c - m[Zx]*s;      // Y = Ycos - Zsin
        n[Yy] = m[Yy]*c - m[Zy]*s;
        n[Yz] = m[Yz]*c - m[Zz]*s;

        n[Zx] = m[Yx]*s + m[Zx]*c;      // Z = Ysin + Zcos
        n[Zy] = m[Yy]*s + m[Zy]*c;
        n[Zz] = m[Yz]*s + m[Zz]*c;
        break;

        // Y : Yaw
        case AXIS_Y:
        n[Xx] = m[Xx]*c - m[Zx]*s;      // X = Xcos - Zsin
        n[Xy] = m[Xy]*c - m[Zy]*s;
        n[Xz] = m[Xz]*c - m[Zz]*s;

        n[Zx] = m[Xx]*s + m[Zx]*c;      // Z = Xsin + Zcos
        n[Zy] = m[Xy]*s + m[Zy]*c;
        n[Zz] = m[Xz]*s + m[Zz]*c;
        break;

        // Z : Roll
        case AXIS_Z:
        n[Xx] = m[Xx]*c - m[Yx]*s;      // X = Xcos - Ysin
        n[Xy] = m[Xy]*c - m[Yy]*s;
        n[Xz] = m[Xz]*c - m[Yz]*s;

        n[Yx] = m[Xx]*s + m[Yx]*c;      // Y = Xsin + Ycos
        n[Yy] = m[Xy]*s + m[Yy]*c;
        n[Yz] = m[Xz]*s + m[Yz]*c;
        break;

        default: ASSERT(0); return;
    }

    *this = n;  // dest = src
}

/*****************************************************************************
 * Rotate matrix around local axis.
 * Rotate a local coordinate system around its own axis.
 * This function is suited to rotating an independent object.
 * The rotation is relative to local coodinate system (not the fixed/eye system).
 * The trick is to load an identity-mapped matrix and rotate it, then transform
 * it thru the given matrix (which defines the local coordinate system)
 * as though it was the coords (1.0, 1.0, 1.0).  These coords of course define
 * the X,Y,Z axises.  The transformation is effectively a local rotation.
 *****************************************************************************/
void
Matrix::RotateLocal( uint axis, Radian rad )
{
    // Identity (1:1) matrix r.
    Matrix r;

    // Rotate matrix r.
    r.RotateFixed( axis, rad );

    // Transform r thru m.
    // Ie, thru matrix m, pass r as if it were the rotated coords (1.0, 1.0, 1.0).
    Matrix t;
    t[Xx] = r.RotateTranslateX( m[Xx], m[Xy], m[Xz] );
    t[Xy] = r.RotateTranslateY( m[Xx], m[Xy], m[Xz] );
    t[Xz] = r.RotateTranslateZ( m[Xx], m[Xy], m[Xz] );

    t[Yx] = r.RotateTranslateX( m[Yx], m[Yy], m[Yz] );
    t[Yy] = r.RotateTranslateY( m[Yx], m[Yy], m[Yz] );
    t[Yz] = r.RotateTranslateZ( m[Yx], m[Yy], m[Yz] );

    t[Zx] = r.RotateTranslateX( m[Zx], m[Zy], m[Zz] );
    t[Zy] = r.RotateTranslateY( m[Zx], m[Zy], m[Zz] );
    t[Zz] = r.RotateTranslateZ( m[Zx], m[Zy], m[Zz] );

    // m = r excluding origin elements.
    m[Xx] = t[Xx];
    m[Xy] = t[Xy];
    m[Xz] = t[Xz];

    m[Yx] = t[Yx];
    m[Yy] = t[Yy];
    m[Yz] = t[Yz];

    m[Zx] = t[Zx];
    m[Zy] = t[Zy];
    m[Zz] = t[Zz];
}

</pre>

<!-- ********************************* END ********************************* -->
<hr>
<p align='center'>
<font size='-2'>
<!-- hhmts start -->
Last modified: Sat Nov  7 14:44:41 CST 2009
<!-- hhmts end -->
</font>
</p>

</body>
</html>
